package com.zh.index.btree.model;

import com.zh.index.IndexInterface;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Created by Administrator on 2021/7/24.
 * 数据可视化 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
 */
public class BtreeIndex<T extends Comparable> implements IndexInterface {

    private int size = 0;

    /**  达到该元素个数后会进行分裂操作 **/
    private int MaxDegree = 4;

    /**  当前树的最大层数 **/
    private int floor = 0;

    /**  数据节点头 **/
    private DataNode<T> headDataNode;

    /**  叶子节点或分支节点,头节点 **/
    private Node<T> headNode;

    public BtreeIndex(int maxDegree) {
        if (maxDegree < 3)
            maxDegree = 3;
        this.MaxDegree = maxDegree;
    }

    public BtreeIndex(){};

    public boolean add(T t) {
        boolean f = _add(t);
        if (f)
            size++;
        return f;
    }

    public boolean delete(T t) {
        boolean f = _del(t);
        if (f)
            size--;
        return f;
    }

    private boolean _del(T t) {
        DataNode<T> node = findLeftDataNode(t);
        if (null == node || node.compareTo(t) != 0)
            return false;
        LeafNode<T> leafNode = node.getParentNode();
        leafNode.delDataNode(node);
        return true;
    }

    /**
     * 添加数据
     * @param t 需要添加的数据
     * @return 添加成功返回 true, 否则返回 false
     */
    private boolean _add(T t) {
        DataNode dataNode = new DataNode(t);
        // 第一次添加节点
        if (null == headDataNode) {
            this.headDataNode = dataNode;
            LeafNode ln = new LeafNode();
            ln.addDataNode(dataNode);
            this.headNode = ln;
            floor = 1;
            return true;
        }
        DataNode<T> node = findLeftDataNode(t);
        boolean f = null == node;
        if (f)
            node = this.headDataNode;
        else if (node.compareTo(t) == 0)
            return false;
        LeafNode leafNode = node.getParentNode();
        leafNode.addDataNode(dataNode);
        if (leafNode.size() >= MaxDegree) {
            Node<T> head = leafNode.divisionNode(MaxDegree);
            if (null != head) {
                this.headNode = head;
                this.floor++;
            }
        }
        if (f)
            this.headDataNode = dataNode;
        return true;
    }

    /**
     * 查找最接近 t 的节点或略小于 t 的节点
     * @param t
     * @return 如果有 t 相同的节点, 则返回该节点
     * 如果没有与当前节点相同的节点,则返回略小与 t 的节点
     * 如果没有略小于 t 的节点, 则返回 null
     */
    protected DataNode<T> findLeftDataNode(T t) {
        return this.headNode.findLeftDataNode(t);
    }

    public static void main(String[] args) {
        BtreeIndex<Integer> bi = new BtreeIndex<>(4);

        for (int i = 20; i > 0; i -= 2)
            bi.add(i);

        for (int i = 1; i < 20; i += 2) {
            bi.add(i);
            System.out.println(i + "  :: " + bi.aabb());
        }
//        System.out.println( "  :: " + bi.aabb());
//        bi.add(2);
    }

    public String allDataNodeToString() {
        DataNode<T> temp = this.headDataNode;
        StringBuffer sb = new StringBuffer(128);
        while (temp != null) {
            sb.append(temp.getT()).append(":").append(temp.getParentNode().t).append(", ");
            temp = temp.nextDataNode;
        }
        return sb.toString();
    }

    private String aabb() {
        StringBuffer sb = new StringBuffer(size << 3);
        List<Node<T>> ln = new ArrayList<>(size << 1);
        ln.add(this.headNode);
        for (int i = 0; i < ln.size(); i++) {
            Node<T> temp = ln.get(i);
            sb.append(temp.toString());
            if (temp instanceof BranchNode) {
                BranchNode<T> btemp = (BranchNode) temp;
                Iterator<BranchInnerNode<T>> it =  btemp.iterator();
                while (it.hasNext()) {
                    BranchInnerNode<T> innerNode = it.next();
                    ln.add(innerNode.leftChildrenNode);
                    if (null != innerNode.rightChildrenNode)
                        ln.add(innerNode.rightChildrenNode);
                }
            }

        }
        return sb.toString();

    }
}
